<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="utf-8">
	<title>Octree - Three.js Docs</title>
	<meta name="viewport" content="width=device-width, user-scalable=no, minimum-scale=1.0, maximum-scale=1.0">
	<script src="../scripts/highlight.min.js"></script>
	<link type="text/css" rel="stylesheet" href="../styles/highlight-three.css">
	<link type="text/css" rel="stylesheet" href="../styles/page.css">
</head>
<body>
	<h1 translate="no">Octree</h1>
		<section>
			<header>
				<div class="class-description"><p>An octree is a hierarchical tree data structure used to partition a three-dimensional
space by recursively subdividing it into eight octants.</p>
<p>This particular implementation can have up to sixteen levels and stores up to eight triangles
in leaf nodes.</p>
<p><code>Octree</code> can be used in games to compute collision between the game world and colliders from
the player or other dynamic 3D objects.</p></div>
				<h2>Code Example</h2>
				<div translate="no"><pre><code class="language-js">const octree = new Octree().fromGraphNode( scene );
const result = octree.capsuleIntersect( playerCollider ); // collision detection
</code></pre></div>
			</header>
			<article>
				<h2 class="subsection-title">Import</h2>
				<p><span translate="no">Octree</span> is an addon, and must be imported explicitly, see <a href="https://threejs.org/manual/#en/installation" target="_blank" rel="noopener">Installation#Addons</a>.</p>
				<pre><code class="language-js">import { Octree } from 'three/addons/math/Octree.js';</code></pre>
				<div class="container-overview">
					<h2>Constructor</h2>
					<h3 class="name name-method" id="Octree" translate="no">new <a href="#Octree">Octree</a><span class="signature">( box : <span class="param-type"><a href="Box3.html">Box3</a></span> )</span> </h3>
					<div class="method">
						<div class="description">
							<p>Constructs a new Octree.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>box</strong>
									</td>
									<td class="description last">
										<p>The base box with enclose the entire Octree.</p>
									</td>
								</tr>
							</tbody>
						</table>
					</div>
				</div>
				<h2 class="subsection-title">Properties</h2>
				<div class="member">
					<h3 class="name" id="bounds" translate="no">.<a href="#bounds">bounds</a><span class="type-signature"> : <a href="Box3.html">Box3</a></span> </h3>
					<div class="description">
						<p>The bounds of the Octree. Compared to <a href="Octree.html#box">Octree#box</a>, no
margin is applied.</p>
					</div>
				</div>
				<div class="member">
					<h3 class="name" id="box" translate="no">.<a href="#box">box</a><span class="type-signature"> : <a href="Box3.html">Box3</a></span> </h3>
					<div class="description">
						<p>The base box with enclose the entire Octree.</p>
					</div>
				</div>
				<div class="member">
					<h3 class="name" id="layers" translate="no">.<a href="#layers">layers</a><span class="type-signature"> : <a href="Layers.html">Layers</a></span> </h3>
					<div class="description">
						<p>Can by used for layers configuration for refine testing.</p>
					</div>
				</div>
				<div class="member">
					<h3 class="name" id="maxLevel" translate="no">.<a href="#maxLevel">maxLevel</a><span class="type-signature"> : number</span> </h3>
					<div class="description">
						<p>The maximum level of the Octree. It defines the maximum
hierarchical depth of the data structure.</p>
						<p>Default is <code>16</code>.</p>
					</div>
				</div>
				<div class="member">
					<h3 class="name" id="trianglesPerLeaf" translate="no">.<a href="#trianglesPerLeaf">trianglesPerLeaf</a><span class="type-signature"> : number</span> </h3>
					<div class="description">
						<p>The number of triangles a leaf can store before it is split.</p>
						<p>Default is <code>8</code>.</p>
					</div>
				</div>
				<h2 class="subsection-title">Methods</h2>
					<h3 class="name name-method" id="addTriangle" translate="no">.<a href="#addTriangle">addTriangle</a><span class="signature">( triangle : <span class="param-type"><a href="Triangle.html">Triangle</a></span> )</span><span class="type-signature"> : <a href="Octree.html">Octree</a></span> </h3>
					<div class="method">
						<div class="description">
							<p>Adds the given triangle to the Octree. The triangle vertices are clamped if they exceed
the bounds of the Octree.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>triangle</strong>
									</td>
									<td class="description last">
										<p>The triangle to add.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> A reference to this Octree.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="boxIntersect" translate="no">.<a href="#boxIntersect">boxIntersect</a><span class="signature">( box : <span class="param-type"><a href="Box3.html">Box3</a></span> )</span><span class="type-signature"> : Object | boolean</span> </h3>
					<div class="method">
						<div class="description">
							<p>Performs a bounding box intersection test with this Octree.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>box</strong>
									</td>
									<td class="description last">
										<p>The bounding box to test.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> The intersection object. If no intersection
is detected, the method returns <code>false</code>.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="build" translate="no">.<a href="#build">build</a><span class="signature">()</span><span class="type-signature"> : <a href="Octree.html">Octree</a></span> </h3>
					<div class="method">
						<div class="description">
							<p>Builds the Octree.</p>
						</div>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> A reference to this Octree.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="calcBox" translate="no">.<a href="#calcBox">calcBox</a><span class="signature">()</span><span class="type-signature"> : <a href="Octree.html">Octree</a></span> </h3>
					<div class="method">
						<div class="description">
							<p>Prepares <a href="Octree.html#box">Octree#box</a> for the build.</p>
						</div>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> A reference to this Octree.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="capsuleIntersect" translate="no">.<a href="#capsuleIntersect">capsuleIntersect</a><span class="signature">( capsule : <span class="param-type"><a href="Capsule.html">Capsule</a></span> )</span><span class="type-signature"> : Object | boolean</span> </h3>
					<div class="method">
						<div class="description">
							<p>Performs a capsule intersection test with this Octree.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>capsule</strong>
									</td>
									<td class="description last">
										<p>The capsule to test.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> The intersection object. If no intersection
is detected, the method returns <code>false</code>.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="clear" translate="no">.<a href="#clear">clear</a><span class="signature">()</span><span class="type-signature"> : <a href="Octree.html">Octree</a></span> </h3>
					<div class="method">
						<div class="description">
							<p>Clears the Octree by making it empty.</p>
						</div>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> A reference to this Octree.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="fromGraphNode" translate="no">.<a href="#fromGraphNode">fromGraphNode</a><span class="signature">( group : <span class="param-type"><a href="Object3D.html">Object3D</a></span> )</span><span class="type-signature"> : <a href="Octree.html">Octree</a></span> </h3>
					<div class="method">
						<div class="description">
							<p>Constructs the Octree from the given 3D object.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>group</strong>
									</td>
									<td class="description last">
										<p>The scene graph node.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> A reference to this Octree.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="getBoxTriangles" translate="no">.<a href="#getBoxTriangles">getBoxTriangles</a><span class="signature">( box : <span class="param-type"><a href="Box3.html">Box3</a></span>, triangles : <span class="param-type">Array.&lt;<a href="Triangle.html">Triangle</a>></span> )</span> </h3>
					<div class="method">
						<div class="description">
							<p>Computes the triangles that potentially intersect with the given bounding box.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>box</strong>
									</td>
									<td class="description last">
										<p>The bounding box.</p>
									</td>
								</tr>
								<tr>
									<td class="name">
										<strong>triangles</strong>
									</td>
									<td class="description last">
										<p>The target array that holds the triangles.</p>
									</td>
								</tr>
							</tbody>
						</table>
					</div>
					<h3 class="name name-method" id="getCapsuleTriangles" translate="no">.<a href="#getCapsuleTriangles">getCapsuleTriangles</a><span class="signature">( capsule : <span class="param-type"><a href="Capsule.html">Capsule</a></span>, triangles : <span class="param-type">Array.&lt;<a href="Triangle.html">Triangle</a>></span> )</span> </h3>
					<div class="method">
						<div class="description">
							<p>Computes the triangles that potentially intersect with the given capsule.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>capsule</strong>
									</td>
									<td class="description last">
										<p>The capsule to test.</p>
									</td>
								</tr>
								<tr>
									<td class="name">
										<strong>triangles</strong>
									</td>
									<td class="description last">
										<p>The target array that holds the triangles.</p>
									</td>
								</tr>
							</tbody>
						</table>
					</div>
					<h3 class="name name-method" id="getRayTriangles" translate="no">.<a href="#getRayTriangles">getRayTriangles</a><span class="signature">( ray : <span class="param-type"><a href="Ray.html">Ray</a></span>, triangles : <span class="param-type">Array.&lt;<a href="Triangle.html">Triangle</a>></span> )</span> </h3>
					<div class="method">
						<div class="description">
							<p>Computes the triangles that potentially intersect with the given ray.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>ray</strong>
									</td>
									<td class="description last">
										<p>The ray to test.</p>
									</td>
								</tr>
								<tr>
									<td class="name">
										<strong>triangles</strong>
									</td>
									<td class="description last">
										<p>The target array that holds the triangles.</p>
									</td>
								</tr>
							</tbody>
						</table>
					</div>
					<h3 class="name name-method" id="getSphereTriangles" translate="no">.<a href="#getSphereTriangles">getSphereTriangles</a><span class="signature">( sphere : <span class="param-type"><a href="Sphere.html">Sphere</a></span>, triangles : <span class="param-type">Array.&lt;<a href="Triangle.html">Triangle</a>></span> )</span> </h3>
					<div class="method">
						<div class="description">
							<p>Computes the triangles that potentially intersect with the given bounding sphere.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>sphere</strong>
									</td>
									<td class="description last">
										<p>The sphere to test.</p>
									</td>
								</tr>
								<tr>
									<td class="name">
										<strong>triangles</strong>
									</td>
									<td class="description last">
										<p>The target array that holds the triangles.</p>
									</td>
								</tr>
							</tbody>
						</table>
					</div>
					<h3 class="name name-method" id="rayIntersect" translate="no">.<a href="#rayIntersect">rayIntersect</a><span class="signature">( ray : <span class="param-type"><a href="Ray.html">Ray</a></span> )</span><span class="type-signature"> : Object | boolean</span> </h3>
					<div class="method">
						<div class="description">
							<p>Performs a ray intersection test with this Octree.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>ray</strong>
									</td>
									<td class="description last">
										<p>The ray to test.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> The nearest intersection object. If no intersection
is detected, the method returns <code>false</code>.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="sphereIntersect" translate="no">.<a href="#sphereIntersect">sphereIntersect</a><span class="signature">( sphere : <span class="param-type"><a href="Sphere.html">Sphere</a></span> )</span><span class="type-signature"> : Object | boolean</span> </h3>
					<div class="method">
						<div class="description">
							<p>Performs a bounding sphere intersection test with this Octree.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>sphere</strong>
									</td>
									<td class="description last">
										<p>The bounding sphere to test.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> The intersection object. If no intersection
is detected, the method returns <code>false</code>.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="split" translate="no">.<a href="#split">split</a><span class="signature">( level : <span class="param-type">number</span> )</span><span class="type-signature"> : <a href="Octree.html">Octree</a></span> </h3>
					<div class="method">
						<div class="description">
							<p>Splits the Octree. This method is used recursively when
building the Octree.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>level</strong>
									</td>
									<td class="description last">
										<p>The current level.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> A reference to this Octree.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="triangleBoxIntersect" translate="no">.<a href="#triangleBoxIntersect">triangleBoxIntersect</a><span class="signature">( box : <span class="param-type"><a href="Box3.html">Box3</a></span>, triangle : <span class="param-type"><a href="Triangle.html">Triangle</a></span> )</span><span class="type-signature"> : Object | false</span> </h3>
					<div class="method">
						<div class="description">
							<p>Computes the intersection between the given bounding box and triangle.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>box</strong>
									</td>
									<td class="description last">
										<p>The bounding box to test.</p>
									</td>
								</tr>
								<tr>
									<td class="name">
										<strong>triangle</strong>
									</td>
									<td class="description last">
										<p>The triangle to test.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> The intersection object. If no intersection
is detected, the method returns <code>false</code>.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="triangleCapsuleIntersect" translate="no">.<a href="#triangleCapsuleIntersect">triangleCapsuleIntersect</a><span class="signature">( capsule : <span class="param-type"><a href="Capsule.html">Capsule</a></span>, triangle : <span class="param-type"><a href="Triangle.html">Triangle</a></span> )</span><span class="type-signature"> : Object | false</span> </h3>
					<div class="method">
						<div class="description">
							<p>Computes the intersection between the given capsule and triangle.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>capsule</strong>
									</td>
									<td class="description last">
										<p>The capsule to test.</p>
									</td>
								</tr>
								<tr>
									<td class="name">
										<strong>triangle</strong>
									</td>
									<td class="description last">
										<p>The triangle to test.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> The intersection object. If no intersection
is detected, the method returns <code>false</code>.</dt>
						</dl>
					</div>
					<h3 class="name name-method" id="triangleSphereIntersect" translate="no">.<a href="#triangleSphereIntersect">triangleSphereIntersect</a><span class="signature">( sphere : <span class="param-type"><a href="Sphere.html">Sphere</a></span>, triangle : <span class="param-type"><a href="Triangle.html">Triangle</a></span> )</span><span class="type-signature"> : Object | false</span> </h3>
					<div class="method">
						<div class="description">
							<p>Computes the intersection between the given sphere and triangle.</p>
						</div>
						<table class="params">
							<tbody>
								<tr>
									<td class="name">
										<strong>sphere</strong>
									</td>
									<td class="description last">
										<p>The sphere to test.</p>
									</td>
								</tr>
								<tr>
									<td class="name">
										<strong>triangle</strong>
									</td>
									<td class="description last">
										<p>The triangle to test.</p>
									</td>
								</tr>
							</tbody>
						</table>
						<dl class="details">
							<dt class="tag-returns"><strong>Returns:</strong> The intersection object. If no intersection
is detected, the method returns <code>false</code>.</dt>
						</dl>
					</div>
				<h2 class="subsection-title">Source</h2>
				<p>
					<a href="https://github.com/mrdoob/three.js/blob/master/examples/jsm/math/Octree.js" translate="no" target="_blank" rel="noopener">examples/jsm/math/Octree.js</a>
				</p>
			</article>
		</section>
<script src="../scripts/linenumber.js"></script>
<script src="../scripts/page.js"></script>
</body>
</html>